package lab9;

import java.util.Scanner;

public class Levenshtein {

	static long counter=0;
	/**
	 * Finds the Levenshtein distance of two strings. Very slow recursion.
	 */
	public static int levenshteinDistanceRecursive(String first, String second) {
		counter++;
		if (first.length() == 0)
			return second.length();
		if (second.length() == 0)
			return first.length();
		int differentLastChar = 0;
		if (first.charAt(first.length() - 1) != second.charAt(second.length() - 1))
			differentLastChar = 1;
		String firstNoLastSymbol = first.substring(0, first.length() - 1);
		String secondNoLastSymbol = second.substring(0, second.length() - 1);
		int cutFirst = levenshteinDistanceRecursive(firstNoLastSymbol, second) + 1;
		int cutSecond = levenshteinDistanceRecursive(first, secondNoLastSymbol) + 1;
		int cutBoth = levenshteinDistanceRecursive(firstNoLastSymbol, secondNoLastSymbol)
				+ differentLastChar;
		return min(cutFirst, cutSecond, cutBoth);
	}
	
	/**
	 * Finds the Levenshtein distance of two strings. Way faster version.
	 */
	public static int levenshteinDistance(String first, String second){
		int[][] solver = new int[first.length()+1][second.length()+1];
		for (int i = 0; i < solver[0].length; i++) solver[0][i]=i;
		for (int i = 0; i < solver.length; i++) solver[i][0]=i;
		for (int i = 1; i <= first.length(); i++) {
			for (int j = 1; j <= second.length(); j++) {
				if (first.charAt(i-1)==second.charAt(j-1)) solver[i][j]=solver[i-1][j-1];
				else {
					int a = solver[i-1][j] + 1;
					int b = solver[i][j-1] + 1;
					int c = solver[i-1][j-1] + 1;
					solver[i][j] = min (a, b, c);
				}
				counter++;
			}
		}
		return solver[solver.length-1][solver[0].length-1];
	}

	/**
	 * Finds the minimal of 3 ints
	 */
	private static int min(int a, int b, int c) {
		if (a <= b && a <= c)
			return a;
		if (b <= c)
			return b;
		return c;
	}

	/**
	 * Test function
	 */
	public static void main(String[] args) {
		Scanner sc = new Scanner(System.in);
		String first = sc.nextLine();
		String second = sc.nextLine();
//		System.out.println("Using recurrsion: " + levenshteinDistanceRecursive(first, second));
//		System.out.println(counter + " iterations.");
//		counter=0;
		System.out.println("Using a matrix: " + levenshteinDistance(first, second));
		System.out.println(counter + " iterations.");
	}

}
